//
//  main.c
//  107. levelOrderBottom
//
//  Created by edz on 2020/7/13.
//  Copyright © 2020 edz. All rights reserved.
//

/*
 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 例如：
 给定二叉树 [3,9,20,null,null,15,7],

     3
    / \
   9  20
     /  \
    15   7
 返回其自底向上的层次遍历为：

 [
   [15,7],
   [9,20],
   [3]
 ]

 */

#include <stdio.h>
#include <math.h>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 获取最大深度
int maxDepth(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    }
    int countleft = 1 , countright = 1;
    if (root->left) {
        countleft += maxDepth(root->left);
    }
    if (root->right) {
        countright += maxDepth(root->right);
    }
    return countleft > countright ? countleft : countright;
}

// 获取每一层节点个数
int* num(struct TreeNode* root){
    int num[maxDepth(root)];
    for (int i = 0; i < maxDepth(root); i++) {
        
    }
}

int** levelOrderBottom(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    if (root == NULL) {
        *returnSize = 0;
        return 0;
    }
    int count = 1;
    int flag = 0 ;
    int k = maxDepth(root);
    returnColumnSizes[k-1][0] = root->val;
    for (int i = k-2; i >= 0 ; i--) {
        int n = pow(2, k-1-i);
        for (int j = 0; j < n; j++) {
            flag = 0;
            if (root->left == NULL && root->right == NULL) {
                continue;
            }
            if (root->left == NULL) {
                returnColumnSizes[i][j] = root->right->val;
                flag = 1;
            }
            if (root->right == NULL) {
                returnColumnSizes[i][j] = root->left->val;
                flag = 1;
            }
            else {
                returnColumnSizes[i][j] = root->left->val;
                returnColumnSizes[i][++j] = root->right->val;
                flag = 2;
            }
            root = root->left; // 怎么分left right 两个方向
        }
        count += flag;
    }
    *returnSize =count;
    return returnColumnSizes;
}
